Aprendizado de Máquina I

Hugo Tremonte de Carvalho

hugo@dme.ufrj.br


04 - Métodos não-paramétricos: KNN

Motivação

  • Como aumentar a flexibilidade de \(g(\mathbf{x})\)?
    • \(g\) linear \(\Rightarrow\) incluir termos de maior grau
    • Criar atributos artificiais e manter \(g\) linear
  • Ainda mantém a forma de \(g\) relativamente restrita…
  • Métodos não-paramétricos:
    • Forma de \(g\) livre
    • “Infinitos parâmetros”
    • Requer “mais” dados

\(K\) vizinhos mais próximos (KNN)

KNN - ideia

  • Relembrando: \(Y = r(\mathbf{X}) + \varepsilon\)
    • A relação sistemática entre \(\mathbf{X}\) e \(Y\) é “bem comportada”: \(\mathbf{X}\)’s próximos \(\Rightarrow\) \(Y\)’s semelhantes
  • Usar essa ideia para criar um estimador \(g\)
  • Diga-me com quem andas e te direi quem és

KNN - formalização

\[g(\mathbf{x}) = \frac{1}{k}\sum_{i \in \mathcal{N}_{\mathbf{x}}^{(k)}} y_i,\] onde \(\mathcal{N}_{\mathbf{x}}^{(k)}\) é o conjunto dos índices das \(k\) observações mais próximas de \(\mathbf{x}\), ou seja, \[\mathcal{N}_{\mathbf{x}}^{(k)} = \left\{i \in \{1, \dots, n\} ~ \left| ~ d(\mathbf{x}_i, \mathbf{x}) \leq d_{\mathbf{x}}^k \right\}\right.,\] e \(d_{\mathbf{x}}^k\) representa a distância do \(k\)-ésimo vizinho mais próximo de \(\mathbf{x}\) para \(\mathbf{x}\).

KNN - propriedades

  • Hiperparâmetro \(k\) \(\Rightarrow\) validação cruzada
  • \(k\) alto \(\Rightarrow\) modelo simples
    • \(k \to \infty\) \(\Rightarrow\) \(g\) constante
    • Viés alto, baixa variância
  • \(k\) pequeno \(\Rightarrow\) modelo mais complexo
    • Variância alta, viés baixo
    • Requer mais dados para ser mais fidedigno
    • Quão mais? Veremos mais adiante!

KNN - Exemplo

\(X \sim \mathcal{U}[0, 4]\)

\(f(x) = \sin(\pi x)\)

\(Y = f(X) + \varepsilon\)

\(\varepsilon \sim \mathcal{N}(0, 0.4)\)

KNN - Exemplo

scikit-learn - KNeighborRegressor

KNN = KNeighborsRegressor(n_neighbors = 1)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)
Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

KNN = KNeighborsRegressor(n_neighbors = 5)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)
Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

KNN = KNeighborsRegressor(n_neighbors = 50)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)
Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

KNN = KNeighborsRegressor(n_neighbors = 150)
KNN.fit(x_tr.reshape(-1, 1), y_tr)
print('Dimensões sem reshape :', x_tr.shape)
print('Dimensões com reshape :', x_tr.reshape(-1, 1).shape)
Dimensões sem reshape : (400,)
Dimensões com reshape : (400, 1)

KNN - Exemplo

Encontrando o melhor \(k\) por validação cruzada

KNN = KNeighborsRegressor()
param_grid_KNN = {"n_neighbors": range(1, 31)}
KNNCV = GridSearchCV(KNN, param_grid = param_grid_KNN,
                     scoring='neg_mean_squared_error', cv = 5)
KNNCV.fit(x_tr.reshape(-1, 1), y_tr)
print(KNNCV.best_estimator_)
KNeighborsRegressor(n_neighbors=17)

KNN - Exemplo

Otimizando outros hiperparâmetros por validação cruzada

KNN = KNeighborsRegressor()
param_grid_KNN = {"n_neighbors": range(1, 31),
                  "weights": ['uniform', 'distance'], "p": range(1, 5)}
KNNCV = GridSearchCV(KNN, param_grid = param_grid_KNN, scoring='neg_mean_squared_error', cv = 5)
KNNCV.fit(x_tr.reshape(-1, 1), y_tr)
print(KNNCV.best_estimator_, "Weights: ", KNNCV.best_estimator_.weights)
KNeighborsRegressor(n_neighbors=17, p=1) Weights:  uniform

KNN - Observações

  • Jogamos algumas coisas pra baixo do tapete!
    • algorithm
    • leaf_size
  • See Nearest Neighbors in the online documentation for a discussion of the choice of algorithm and leaf_size.

Distâncias em alta dimensão

A maldição da dimensionalidade 👻

A maldição da dimensionalidade

Being able to sense simultaneously thousands of variables on each ”individual” sounds like good news: Potentially we will be able to scan every variable that may influence the phenomenon under study. The statistical reality unfortunately clashes with this optimistic statement: Separating the signal from the noise is in general almost impossible in high-dimensional data. This phenomenon […] is often called the ‘curse of dimensionality’.

A maldição da dimensionalidade

The impact of high dimensionality on statistics is multiple. First, high-dimensional spaces are vast and data points are isolated in their immensity. Second, the accumulation of small fluctuations in many different directions can produce a large global fluctuation. Third, an event that is an accumulation of rare events may not be rare. Finally, numerical computations and optimizations in high-dimensional spaces can be overly intensive.

Fonte: Christophe Giraud - Introduction to High-Dimensional Statistics

Distâncias em alta dimensão

  • Conjunto de \(n\) observações
  • Cada observação é um vetor de \(p\) atributos
    • Cada entrada uniformemente distribuída em \((0, 1)\)
  • Chamaremos tal conjunto de dados de \(\mathbf{X}\)
  • Consideremos os cenários \(n \approx p\) ou mesmo \(n < p\)
  • Calcular distâncias entre pares distintos de observações
    • Linhas da matriz \(\mathbf{X}\)
  • Agradecimento: Códigos de Lucas Galdino (Projetos 01 e 02 da edição de 2022/02 dessa disciplina)

Histogramas para \(p\) pequeno

Histogramas à medida que \(p\) cresce

O que está acontecendo?

  • \(p\) cresce \(\Rightarrow\) gráficos com o mesmo “formato” e se “deslocando” para a direita
  • Possíveis hipóteses:
    • O desvio padrão é constante à medida que \(p\) cresce
    • A média cresce à medida que \(p\) cresce
  • Vamos verificá-las!

Uma definição preliminar

  • Definição: Dada uma variável aleatória \(X\) com média diferente de zero, definimos o seu coeficiente de variação como \[\mathrm{cv}(X) = \frac{\sqrt{\mathbb{V}(X)}}{\mathbb{E}[X]}.\]

Calculando o coeficiente de variação

Dimensão (p) Coeficiente de variação
0 1 0.706066
1 2 0.479571
2 3 0.365652
3 4 0.319981
4 5 0.288417
5 6 0.254690
6 7 0.234621
7 8 0.215403
8 9 0.209124
9 10 0.189904
10 100 0.059053
11 1000 0.019566
12 10000 0.006003
13 100000 0.001834
14 1000000 0.000581

Interpretando a tabela

  • \(p\) cresce \(\Rightarrow\) o coeficiente de variação é cada vez mais próximo de zero
  • Possível conclusão: quando \(p\to \infty\), temos que \(\mathrm{cv} \to 0\)
  • Mas como se dá essa convergência?

Estudando \(\mathrm{cv} \to 0\)

Dimensão (p) Desvio padrão Média
0 1 0.235095 0.332964
1 2 0.234640 0.489271
2 3 0.253379 0.692950
3 4 0.246943 0.771743
4 5 0.250732 0.869337
5 6 0.252654 0.992007
6 7 0.249233 1.062280
7 8 0.242561 1.126082
8 9 0.247946 1.185640
9 10 0.244178 1.285802
10 100 0.241119 4.083056
11 1000 0.252474 12.903961
12 10000 0.244872 40.789564
13 100000 0.236771 129.097221
14 1000000 0.237349 408.246510

Interpretando a nova tabela

  • Desvio padrão parece estabilizar-se (ou crescer muito devagar)
  • A média parece crescer
  • Verifiquemos isso rigorosamente!
  • \(\mathbf{X}^{(i)}\) e \(\mathbf{X}^{(j)}\) duas linhas distintas da matriz \(\mathbf{X}\): \[\frac{\sqrt{\mathbb{V}\left(\left\|\mathbf{X}^{(i)} - \mathbf{X}^{(j)}\right\|^2\right)}}{\mathbb{E}\left[\left\|\mathbf{X}^{(i)} - \mathbf{X}^{(j)}\right\|^2\right]} \propto \frac{1}{\sqrt{p}}.\]

O que isso tem a ver com o KNN?

  • KNN é baseado em distâncias
  • Em alta dimensão, a noção de “distância” é curiosa!
  • Pontos mais “espaçados” entre si
  • Possível perda de capacidade preditiva do KNN

Um pequeno experimento

  • \(\mathbf{X}\) matriz \(n \times p\), com \(p \gg n\)
  • Entradas uniformes em \((0, 1)\)
  • Fixar a primeira linha de \(\mathbf{X}\)
  • Calcular a proporção da menor distância para outro vetor linha de \(\mathbf{X}\) pela média da distâncias para todos os outros vetores linha de \(\mathbf{X}\)

Um pequeno experimento

Dimensão (p) menor dist/dist média
0 1 0.001487
1 5 0.187291
2 10 0.364847
3 50 0.776107
4 100 0.813959
5 500 0.909649
6 1000 0.942657
7 5000 0.974147
8 10000 0.980400
9 50000 0.992058
10 100000 0.993582

Conclusão para o KNN

  • \(p \to \infty\) \(\Rightarrow\) proporção tende a 1
  • À medida que \(p\) cresce, a menor distância e a distância média são cada vez mais similares
  • A noção de \(K\) vizinhos mais próximos perde sentido!